Binary-Tree —— Recursion

发表于 | 分类于 | | 热度: ℃
字数统计: 1,969 | 阅读时长 ≈ 8

0x00 递归模板

递归原理

树可以以递归的方式定义为一个节点（根节点），它包括一个值和一个指向其他节点指针的列表。递归是树的特性之一，对于每个递归层级，我们只能关注单个节点内的问题，并通过递归调用函数来解决其子节点问题。通常，我们可以通过自顶向下或自底向上的递归来解决树的问题。

“自顶向下”解决方案

“自顶向下”意味着在每个递归层级，我们首先访问节点来计算一些值，并在递归调用函数时将这些值传递到子节点。所以”自顶向下”的解决方案可以被认为是一种前序遍历。具体来说，递归函数top_down(root, params)的模板如下：

1
2
3
4
5
1.return specific value for null node
2.update the answer if needed                       // answer <-- params
3.left_answer = top_down(root.left, left_params)    // left_params <-- root.val, params
4.right_answer = top_down(root.right, right_params) // right_params <-- root.val, params
5.return the answer if needed                       // answer <-- left_answer, right_answer

“自底向上”解决方案

“自底向上”是另一种递归方法。在每个递归层次上，我们首先对所有子节点递归地调用函数，然后根据返回值和根节点本身地值得到答案。这个过程可以看作是后序遍历的一种。通常，”自底向上”的递归函数bottom_up(root)的模板如下：

1
2
3
4
1.return specific value for null node
2.left_answer = bottom_up(root.left)      // call function recursively for left node
3.right_answer = bottom_up(root.right)    // call function recursively for right node
4.return answers                          // answer <-- left_answer, right_answer, root.val

总结

使用递归方法解决树的相关问题时，可以从以下几个角度考虑。

能否确定一些参数，从该节点自身出发寻找答案？

能否使用这些参数和节点本身的值决定传递给其子节点的参数？

如果上述两个问题的答案都是肯定的，那么可以尝试使用自顶向下的递归来解决此问题。在无法给出确定答案的情况下，我们思考下面的问题：

对于树中的任意一个节点，在已知其子节点答案的情况下，能否计算出该节点的答案？

如果上述问题的答案是肯定的，那么自底向上的递归可能是一个不错的解决方法。

0x01 典型题目

这里选取LeetCode上二叉树卡片第二部分“运用递归解决问题”中的三道题目作为典型题目来深入说明递归这一方法在解决二叉树问题上的使用。

LeetCode-104.Maximum Depth of Binary Tree

题目链接

104.Maximum Depth of Binary Tree

题目描述

104.PNG-15.9kB

思路分析

本题目可以使用两种递归方法解决——自顶向下和自底向上。

方法一： 自顶向下

自顶向下的递归方法需要提前定义一个私有变量result来记录最终的结果。递归函数中，若输入节点为null则直接返回；若输入节点为叶子节点，则返回result与当前深度的最大值；否则进行先左后右的子树递归，每次递归相当于进入下一层，故将传入的深度加一。该写法中深度的逐渐增加与自顶向下思想契合。

方法二： 自底向上

对于自底向上可以这样理解：对于当前输入的节点，我们需要递归返回以其为根节点的二叉树的最大深度，该深度的计算方法为其左右子树深度的最大值加一。所以对于每层的输入节点，我们首先判断其是否为空，若为空则返回0；否则递归地进行其左右子树深度计算，最终返回其左右子树深度的最大值加一。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 方法一： 自顶向下
class Solution {
    private int result = 0;
    public void getMaxDepth(TreeNode root, int depth){
        if(root == null){
            return;
        }
        // 找到叶子节点
        if(root.left == null && root.right == null){
            // 更新最大深度
            result = Math.max(result, depth);
        }
        getMaxDepth(root.left, depth+1);
        getMaxDepth(root.right, depth+1);
    }
    public int maxDepth(TreeNode root){
        getMaxDepth(root, 1);
        return result;
    }
}
// 方法二： 自底向上
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left_answer = maxDepth(root.left);
        int right_answer = maxDepth(root.right);

        return Math.max(left_answer, right_answer) + 1;
    }
}

LeetCode-101.Symmetric Tree

题目链接

101.Symmetric Tree

题目描述

101.PNG-14.3kB

思路分析

刚开始拿到这个题目的时候卡在了将镜像转换成等价表达式的过程。后来对照题目所给的对称二叉树示例，观察第二行，发现对于第二行的两个节点TreeNode t1 = new TreeNode(2), TreeNode t2 = new TreeNode(2)，其满足以下条件等式：

1
2
3
t1.val == t2.val
t1.right.val == t2.left.val
t1.left.val == t2.right.val

于是可以得出，对于同一层的两个节点，以其为根节点的子树是对称子树的条件是：

  • 两节点的值相等；
  • 左节点的右子树和右节点的左子树相同；
  • 左节点的左子树和右节点的右子树相同。

所以我们构造递归函数需要传入两个TreeNode类型的变量。下面我们考虑输入的两个节点变量的可能值。

如果两个节点均为空，说明两节点相等，此时返回true；

如果两个节点有一个为空，说明整棵二叉树不可能为对称子树（题目中所给的第二个二叉树），此时返回false；

如果两个节点均不为空，则比较其值是否相等，并同时递归比较左节点t1的右子节点和右节点t2的左子节点是否相同以及左节点t1的左子节点和右节点t2的右子节点是否相同。

对于输入二叉树的原始root节点，我们将(root, root)节点对传入递归函数即可。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }
    public boolean isMirror(TreeNode root1, TreeNode root2){
        if(root1 == null && root2 == null){
            return true;
        }
        if(root1 == null || root2 == null){
            return false;
        }
        return (root1.val == root2.val) && isMirror(root1.left, root2.right) && isMirror(root1.right, root2.left);
    }
}

LeetCode-112.Path Sum

题目链接

112.Path Sum

题目描述

112.PNG-19.1kB

思路分析

本题目要求找加和为sum的二叉搜索路径，我们可以分析输入递归函数节点可能的情况：

若输入节点为空节点，直接返回false；

若输入节点为叶子节点，则比较该节点的值与传入的sum值是否相等；

递归函数的返回值处需要对输入节点的左右子节点分别进行递归，并改变sum值为sum - root.val，题目要求找到一条合理路径即可，故两递归函数使用或连接。

解题代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null){
            return false;
        }
        if(root.left == null && root.right == null){
            return (sum == root.val);
        }
        return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
    }
}

0x02 递归函数构造

使用递归法解决二叉树相关搜索问题的重点就是递归函数的构造。现总结递归函数构造过程如下：

Step1：确定递归函数的返回类型，一般与题目要求的返回类型一致；

Step2：确定递归函数传入的参数；

Step3：考虑传入参数可能出现的全部情况，每种情况分别进行处理，处理过程需要体现递归进行的条件和递归终止的条件；

Notice：一般将根节点的左子树和右子树作为参数先后传入递归函数进行递归过程。

请作者吃个小鱼饼干吧
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多